package SwordFingerOffer;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

public class Q59_WindowMax {
    //滑动窗口最大值
    //给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
    //肯定是需要空间支持的
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0){
            return new int[]{};
        }
        //检查
        int right = 0;
        int [] ans = new int[nums.length - k + 1];
        //容器支持 ==> 单调队列 ==> 头到尾按递减顺序 ==> 存放下标
        Deque<Integer> deque = new LinkedList<>();
        int index = 0; //下标
        for (right = 0; right < nums.length; right++) {
            //保持递减序列
            while (!deque.isEmpty() && nums[right] > nums[deque.peekLast()]){
                deque.pollLast();
            }
            deque.addLast(right);

            //最大值过期处理
            //放的是下标哟
            if (right - k == deque.peekFirst()){
                deque.pollFirst();
            }
            //答案收集
            if (right >= k - 1){
                ans[index++] = nums[deque.peekFirst()];
            }

        }
       return ans;
    }

    public static void main(String[] args) {
        Q59_WindowMax fun = new Q59_WindowMax();
        System.out.println(Arrays.toString(fun.maxSlidingWindow(new int[]{1, 3, -1, -3, 5, 3, 6, 7}, 3)));
    }
}
